package BFS解决FloodFill算法;

import java.util.LinkedList;
import java.util.Queue;

public class test4 {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int n,m;
    public void solve(char[][] board) {
        // 处理这种被包围的问题就是通过先遍历边界,将边界中0进行标记,标记为. --> 这样就可以直接遍历中间部分
        // 中间部分出现0是肯定满足条件的 就可以直接进行替换了,不在需要计算区域了

        n = board.length;
        m = board[0].length;

        // 边界处理
        for(int i = 0;i<n;i++){
            if(board[i][0]=='O') bfs(board,i,0);
            if(board[i][m-1]=='O') bfs(board,i,m-1);
        }

        for (int j = 0; j < m; j++) {
            if(board[0][j]=='O') bfs(board,0,j);
            if(board[n-1][j]=='O') bfs(board,n-1,j);
        }

        // 进行最终处理,将所有的字符进行替换
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == '.') board[i][j] = 'O';
            }
        }
    }
    public void bfs(char[][] board,int sr,int sc){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr,sc});
        board[sr][sc] = '.';

        while (!queue.isEmpty()){
            int[] arr = queue.poll();
            int a = arr[0],b=arr[1];
            for (int i = 0; i < 4; i++) {
                int x = a+dx[i];
                int y = b+dy[i];
                if(x>=0&&x<n&&y>=0&&y<m&&board[x][y]=='O'){
                    board[x][y] = '.';
                    queue.add(new int[]{x,y});
                }
            }
        }
    }
}
